0593. 有效的正方形【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 几何判定

1. 📝 题目描述

• leetcode

给定 2D 空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true。

点的坐标 pi 表示为 [xi, yi]。 输入没有任何顺序。

一个 有效的正方形 有四条等边和四个等角(90 度角)。

---

示例 1：

输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: true

示例 2：

输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出：false

示例 3：

输入：p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
输出：true

---

提示：

• p1.length == p2.length == p3.length == p4.length == 2
• -10^4 <= xi, yi <= 10^4

2. 🎯 s.1 - 几何判定

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

bool validSquare(int* p1, int p1Size, int* p2, int p2Size, int* p3, int p3Size, int* p4, int p4Size) {
    int dist(int* a, int* b) {
        return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]);
    }
    int d[6] = {
        dist(p1,p2), dist(p1,p3), dist(p1,p4),
        dist(p2,p3), dist(p2,p4), dist(p3,p4)
    };
    qsort(d, 6, sizeof(int), cmp);
    return d[0] > 0 && d[0] == d[1] && d[1] == d[2] && d[2] == d[3] && d[4] == d[5];
}

js

/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 */
var validSquare = function (p1, p2, p3, p4) {
  const dist = (a, b) => (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
  const dists = [
    dist(p1, p2),
    dist(p1, p3),
    dist(p1, p4),
    dist(p2, p3),
    dist(p2, p4),
    dist(p3, p4),
  ].sort((a, b) => a - b)
  return (
    dists[0] > 0 &&
    dists[0] === dists[1] &&
    dists[1] === dists[2] &&
    dists[2] === dists[3] &&
    dists[4] === dists[5]
  )
}

py

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        def dist(a, b):
            return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
        d = sorted([dist(p1,p2), dist(p1,p3), dist(p1,p4),
                    dist(p2,p3), dist(p2,p4), dist(p3,p4)])
        return d[0] > 0 and d[0] == d[1] == d[2] == d[3] and d[4] == d[5]

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

算法思路：

• 计算 4 个点之间的 6 个距离的平方并排序
• 正方形应有 4 条相等的边和 2 条相等的对角线，且边长不为 0